#include "enumeration.h"

VertexStack c;

double lim;
long set;
long sets;
long violates;
double k[MAX_VALUE];/*a soma do que vem de fora do conjuto para cada vertice*/
double min[MAX_VALUE];/* vetor das menores arestas de cada vertice*/
long order[MAX_VALUE];
VertexStack v0;/* o v0 para a funcao beta*/
double violates2;
double violates22;
double limcut;

void printSet(long* f){
	long ka;
	fprintf(out,"***********************************************************************");
	fprintf(out,"\n Vertices do conjunto  violado \n");
	for(ka = 0 ; ka< c.size; ka++){
                fprintf(out, " %lu -->> %1.3f o q vem de fora %1.3f\n",c.elems[ka] + 1, weigths[c.elems[ka]][c.elems[ka]], k[c.elems[ka]]);
	}
	fprintf(out, "\nFunção de Tutela para a qual está violado: \n");
	for(ka = 0 ; ka< c.size; ka++){
                if(f[ka] > -1){
                	fprintf(out, "\n %lu -----> %lu e valor da aresta: %1.3f e o valor do q vem de fora : %1.3f",c.elems[ka] + 1,c.elems[f[ka]] + 1,weigths[c.elems[ka]][c.elems[f[ka]]], k[c.elems[f[ka]]]);
                }
	}
	fprintf(out, "\n");
}

//para testes
void printSetFull(long* f, double lim){
	long ka;
	fprintf(out,"***********************************************************************");
	fprintf(out,"\n Valor da função \n", lim);
	fprintf(out,"\n Vertices do conjunto  violado \n");
	for(ka = 0 ; ka< c.size; ka++){
                fprintf(out, " %lu -->> %1.3f o q vem de fora %1.3f\n",c.elems[ka] + 1, weigths[c.elems[ka]][c.elems[ka]], k[c.elems[ka]]);
	}
	fprintf(out, "\nFunção de Tutela para a qual está violado: \n");
	for(ka = 0 ; ka< c.size; ka++){
                if(f[ka] > -1){
                	fprintf(out, "\n %lu -----> %lu e valor da aresta: %1.3f e o valor do q vem de fora : %1.3f",c.elems[ka] + 1,c.elems[f[ka]] + 1,weigths[c.elems[ka]][c.elems[f[ka]]], k[c.elems[f[ka]]]);
                }
	}
	fprintf(out, "\n");
}

int initVar(){
	c.size = 0;
	violates2 = 0;
	violates22 = 0;
	limcut = 0;
	v0.size = 0;
	long i,j,p = 0;
	for(i= 0; i < n; i++){
		if(weigths[va[i]][va[i]] < 1){
			p++;
		}
		min[va[i]] = weigths[va[i]][va[i]];
		k[va[i]] =0.0;
		for(j = 0; j< n; j++){
			/*IMPORTANTE: suponho que se a aresta entre eles naum existe entauma variave kl vake zero*/
			if(i != j)k[va[i]] = k[va[i]] + weigths[va[j]][va[i]];
		}
	}
	for(i = 0; i < n; i++){
		order[va[i]] = i;
	}
	set = 0;
	sets=0;
	violates =0;
	lim =0;
	return 0;
}

int violatedSets( long nV){
	initVar();
	int numZero = 0;
	long R[nV];
	long R0[nV];
	long size = 0;
	long size0 = 0;
	long i,j;
	int t = 0;
	for(i = 0; i< n; i++){
		if(weigths[va[i]][va[i]] < 0.9){/*naum pode tirar os vertices 0 por causa do v_{0} e dos f's*/
			if(weigths[va[i]][va[i]] > 0.1){
                		R[size] = va[i];
                		size++;
			}
			else{
				for(j = 0; j< n; j++){
					if(weigths[va[j]][va[i]] > 0.9){
						t = 1;
                   		 	}
			    	}
                		if(t == 0){
                    			R0[size0] = va[i];
                    			size0++;
                		}	
                		t = 0;
			}
		}
	}
	return enumerateViolatedSets(size,R, size0, R0);
}

int enumerateViolatedSets(long nV, long *R, long nV0, long *R0){
	long j, i,p;
	j = 0;
	while(j < nV){
		lim += weigths[R[j]][R[j]];
		c.elems[c.size] = R[j];
		c.size++;
		for(i = 0; i < nV; i++){
			if(i!=j) k[R[i]] -= weigths[R[j]][R[i]];
			if((i < c.size)&&(min[c.elems[i]] > weigths[c.elems[i]][c.elems[c.size - 1]])&&(i != j))
				min[c.elems[i]] = weigths[c.elems[i]][R[j]];
		}
	    	for(i = 0; i < nV0; i++){
			if(i!=j)k[R0[i]] -= weigths[R[j]][R0[i]];
		}		if(c.size <= 4){
			v0.elems[v0.size] = c.elems[c.size-1];
			v0.size++;
		}else{
			if(min[v0.elems[v0.size-1]] + k[v0.elems[v0.size-1]] > min[c.elems[c.size -2]] + k[c.elems[c.size-2]]){
				v0.elems[v0.size] = c.elems[c.size -2];
				v0.size++;
			}else{
				v0.elems[v0.size] = v0.elems[v0.size-1];
				v0.size++;
			}
		}
		if(lim < 1.9){
			long RR[nV -1];
			long size = 0;
			long RR0[nV0];
			long size0 = 0;
			long cut = 0;
			for(i = j+1; i < nV; i++ ){
				if(hasEdge(c.elems[c.size-1],R[i])){
					RR[size] = R[i];
					size++;
				}
			}
			for(i = 0; i < nV0; i++ ){
				if((hasEdge(c.elems[c.size-1],R0[i]))&&(order[c.elems[c.size-1]] < order[R0[i]])){
					RR0[size0] = R0[i];
					size0++;
				}
			}
			extendSet(size0,RR0,2*c.size);
			enumerateViolatedSets(size, RR, size0, RR0);
		}
		c.size--;
		lim = lim - weigths[R[j]][R[j]];
		for(i = 0; i < nV; i++){
			if(i!=j)k[R[i]] += weigths[R[j]][R[i]];
		}
		for(i = 0; i < nV0; i++){
			if(i!=j)k[R0[i]] += weigths[R[j]][R0[i]];
		}
		v0.size--;
		j++;

	}
	return violates;
}

void extendSet(long nV, long* R, long limite){
    long j, i, p;
	j = 0;
	while((j < nV)&&(c.size < limite)){
		set++;
		if(set % 1000000 == 0){
			sets++;
			printf("kkk estamos agora com %lu000000 conjuntos", sets);
			set = 0;
		}
		c.elems[c.size] = R[j];
		c.size++;
		for(i = 0; i < nV; i++){
			if((i < c.size)&&(min[c.elems[i]] > weigths[c.elems[i]][c.elems[c.size - 1]])&&(i != j))
				min[c.elems[i]] = weigths[c.elems[i]][R[j]];
		}
		if(c.size <= 4){
			v0.elems[v0.size] = c.elems[c.size-1];
			v0.size++;
		}else{
			if(min[v0.elems[v0.size-1]] + k[v0.elems[v0.size-1]] > min[c.elems[c.size -2]] + k[c.elems[c.size-2]]){
				v0.elems[v0.size] = c.elems[c.size -2];
				v0.size++;
			}else{
				v0.elems[v0.size] = v0.elems[v0.size-1];
				v0.size++;
			}
		}
		if(enumerable() == 1){
                	violates++;
		}
		if((lim < 2)&&(c.size <= limite)){
			long RR[nV -1];
			long size = 0;
			for(i = j+1; i < nV; i++ ){
				if(hasEdge(c.elems[c.size-1],R[i])){
					RR[size] = R[i];
					size++;
				}
			}
			extendSet(size,RR, limite);
		}
		c.size--;
		v0.size--;
		j++;
	}
}

double alpha(){
	long i;
	if((k[c.elems[c.size-1]] >= 1)||(k[c.elems[c.size-2]] >= 1)) return 2;
	else{
		double alpha = 0.0;
		for(i =0; i < c.size; i++){
			if(weigths[c.elems[i]][c.elems[i]] < ZERO) alpha += k[c.elems[i]];
		}
		return alpha + lim + k[c.elems[c.size-1]]+ k[c.elems[c.size-2]] + min[c.elems[0]] + min[c.elems[1]];
	}
}

double beta(){
	int i;
	if((k[c.elems[c.size-1]] >= 1)||(k[c.elems[c.size-2]] >= 1)) return 2;
	else{
		double bet = min[v0.elems[v0.size-1]] + k[v0.elems[v0.size-1]];
		for(i =0; i < c.size; i++){
			if(weigths[c.elems[i]][c.elems[i]] < ZERO) bet += k[c.elems[i]];
		}
		return bet + lim + k[c.elems[c.size-1]]+ k[c.elems[c.size-2]] + min[c.elems[0]] + min[c.elems[1]];
	}
}

/*para os tolerantes*/
/*int checkFunction(long* vertex, int numVertex){
	makeSubProblem(vertex,numVertex,k);
	double solution = getSolution();
	long f[numVertex+1];
	if(1) {
		fValue(numVertex, f);
		printSetFull(f, solution + lim );
	}
	return 1;
}*/

/*para os violados*/
int checkFunction(long* vertex, int numVertex){
	makeSubProblem(vertex,numVertex,k);
	double solution = getSolution();
	long f[numVertex+1];
	if(solution + lim < 1.99) {
		violates = violates + 1 ;
		printf("Conjunto Violado encontrado, estamos com %d \n", violates);
		//fValue(numVertex, f);
		//printSet(f);
		return 1;
	}
	return 0;
}


//para os limitantes
/*int enumerable(){	if(c.size >= 4){
		double a = alpha();
		double b = beta();
		if(a < 2 || b < 2){
			violates2 = violates2 + 1;
			return checkFunction(c.elems, c.size);
		}
	}	
	return 0;
}*/

//para os tolerantes
/*int enumerable(){
	if(c.size >= 4){
		return checkFunction(c.elems, c.size);
	}
	return 1;
}*/

/*para os violados*/
int enumerable(){
	int i,j;
	if(c.size >= 4){
		double a = alpha();
		double b = beta();
		/*fprintf(out,"\n Conjunto ....\n ");
		fprintf(out, "\n Valor de alpha: %f",a);
		fprintf(out, "\n Valor de beta: %f",b);
		for(i = 0; i < c.size; i++){
			fprintf(out, "\n vertice = %lu valor =  %f  o q vem de fora = %f ", c.elems[i]+ 1, weigths[c.elems[i]][c.elems[i]],k[c.elems[i]]);
		}*/
		if(a < 2.00 || b < 2.00){
			violates2 = violates2 + 1;
			return checkFunction(c.elems, c.size);
		}
	}	
	return 0;
}
